package BInarySearchTree;

public class BSTBasic<E extends Comparable<E>> {

    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTBasic(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }


    //向二分搜索树添加元素e
    public void add(E e)
    {
        if (root==null)
        {
            root=new Node(e);
            size++;
        }
        else
        {
            add(root,e);
        }
    }

    //向以node为根的二分搜索树中插入元素e，递归算法
    private void add(Node node,E e)
    {
        //递归出口
        if (e.equals(node.e))
            return;
        if (e.compareTo(node.e)<0&&node.left==null)
        {
            node.left=new Node(e);
            size++;
            return;
        }
        if (e.compareTo(node.e)>0&&node.right==null)
        {
            node.right=new Node(e);
            size++;
            return;
        }

        //递归调用
        if (node.e.compareTo(e)<0)
        {
            add(node.left,e);
        }
        else
        {
            add(node.right,e);
        }

    }

}
